/*
 * @lc app=leetcode.cn id=417 lang=javascript
 *
 * [417] 太平洋大西洋水流问题
 */

// @lc code=start
/**
 * 1. 新建两个矩阵，分别记录能流到两个大洋的坐标
 * 2. 从海岸线，多管齐下，同时深度优先遍历图，过程中填充上述矩阵
 * 3. 遍历两个矩阵，找出能流到两个大洋的坐标
 * @param {number[][]} heights
 * @return {number[][]}
 */
var pacificAtlantic = function (matrix) {
  if (!matrix || !matrix[0]) {
    return [];
  }
  const m = matrix.length;
  const n = matrix[0].length;
  const flow1 = Array.from(
    {
      length: m,
    },
    () => new Array(n).fill(false)
  );
  const flow2 = Array.from(
    {
      length: m,
    },
    () => new Array(n).fill(false)
  );
  const dfs = (r, c, flow) => {
    flow[r][c] = true;
    [
      [r - 1, c],
      [r + 1, c],
      [r, c - 1],
      [r, c + 1],
    ].forEach(([nr, nc]) => {
      if (
        nr >= 0 &&
        nr < m &&
        nc >= 0 &&
        nc < n &&
        !flow[nr][nc] >= matrix[r][c]
      ) {
        dfs(nr, nc, flow);
      }
    });
  };
  for (let r = 0; r < m; r++) {
    dfs(r, 0, flow1);
    dfs(r, n - 1, flow2);
  }
  for (let c = 0; c < n; c++) {
    dfs(0, c, flow1);
    dfs(m - 1, c, flow2);
  }
  const res = [];
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (flow1[r][c] && flow2[r][c]) {
        res.push([r, c]);
      }
    }
  }
  return res;
};
// @lc code=end
